Public-key cryptography plays an important role in providing confidentiality, authentication, data integrity, and non-repudiation. The Rivest, Shamir, and Adelman (RSA) algorithm is one widely used in cryptography systems. An RSA operation is a modular exponentiation which requires repeated modular multiplications. RSA operand sizes are often 1024-bits or greater in length. This translates to challenges for systems utilizing RSA in achieving high data throughput rates.
Montgomery multiplication is an efficient method for performing modular multiplication with an arbitrary modulus. It is particularly suitable for implementation on general purpose computing systems such as those implemented by field programmable gate arrays (FPGAs). Montgomery multiplication is based on a representation of a residue class modulo M. The algorithm uses simple divisions by a power of two instead of divisions by M, which are used in a conventional modular operation.
Efforts have been made to increase the performance of Montgomery multipliers implemented on general purpose computing systems by using a high radix Montgomery multiply. This typically involved more complex systems that required the use of higher fixed point multipliers which are not available on all FPGA architectures.
Thus, what is needed is an efficient and effective method and apparatus for increasing the performance of Montgomery multipliers implemented on general purpose computing systems.